package __回溯算法

/*
https://leetcode.cn/problems/subsets/

78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]
*/
var (
	path78 []int
	res78  [][]int
)

func subsets(nums []int) [][]int {
	res78, path78 = make([][]int, 0), make([]int, 0, len(nums))
	dfs78(nums, 0)
	return res78
}
func dfs78(nums []int, start int) {
	tmp := make([]int, len(path78))
	copy(tmp, path78)
	res78 = append(res78, tmp)

	for i := start; i < len(nums); i++ {
		path78 = append(path78, nums[i])
		dfs78(nums, i+1)
		path78 = path78[:len(path78)-1]
	}
}
